"""
难度：简单
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
示例 3：
输入: root = [2,1,3], k = 4
输出: true
示例 4：
输入: root = [2,1,3], k = 1
输出: false
示例 5：
输入: root = [2,1,3], k = 3
输出: true
提示:
二叉树的节点个数的范围是  [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105"""
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def inOrder(self, root, nums):
        if not root:
            return
        self.inOrder(root.left, nums)
        nums.append(root.val)
        self.inOrder(root.right, nums)


    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        nums = []
        self.inOrder(root, nums)
        left, right = 0, len(nums)-1

        while left < right:
            sum = nums[left] + nums[right]
            
            if sum == k:
                return True
            elif sum < k:
                left += 1
            else:
                right -= 1
        return False
        